package date_202403

import "sort"

//473. 火柴拼正方形
//你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
//
//如果你能使这个正方形，则返回 true ，否则返回 false 。
//
//
//
//示例 1:
//
//
//
//输入: matchsticks = [1,1,2,2,2]
//输出: true
//解释: 能拼成一个边长为2的正方形，每边两根火柴。
//示例 2:
//
//输入: matchsticks = [3,3,3,3,4]
//输出: false
//解释: 不能用所有火柴拼成一个正方形。
//
//
//提示:
//
//1 <= matchsticks.length <= 15
//1 <= matchsticks[i] <= 108

func makesquare(matchsticks []int) bool {
	sumLen := 0
	for _, stick := range matchsticks {
		sumLen = sumLen + stick
	}
	if sumLen%4 != 0 {
		return false
	}
	if len(matchsticks) < 4 {
		return false
	}
	sort.Slice(matchsticks, func(i, j int) bool {
		return matchsticks[i] > matchsticks[j]
	})
	if matchsticks[0] > sumLen/4 {
		return false
	}

	edgesLength := make([]int, 4)

	return dfs(0, matchsticks, edgesLength, sumLen/4)
}

func dfs(idx int, matchsticks []int, edgesLength []int, targetNum int) bool {

	// 放完了
	if idx == len(matchsticks) {
		return true
	}

	for i := 0; i < len(edgesLength); i++ {
		edgesLength[i] = edgesLength[i] + matchsticks[idx]
		if edgesLength[i] <= targetNum && dfs(idx+1, matchsticks, edgesLength, targetNum) {
			return true
		}
		edgesLength[i] = edgesLength[i] - matchsticks[idx]
	}
	return false
}
